For it’s difficult to guarantee the accuracy and time efficiency of online map matching simultaneously, an improved online map matching algorithm based on the HMM model is proposed. Different from other global or local algorithms, the algorithm introduces reliable point to divide the trajectory, thus reducing the calculation of transition probability and the output delay of matching results. Also, the method of calculating the transmitting probability by combining distance factor and directional factor is proposed. The algorithm is verified using floating car trajectory data in Seattle. Experimental results show that the proposed algorithm outperforms the traditional HMM map matching algorithm both in accuray and time efficiency, which can meet the requirement of online map matching.